package 树;

import java.util.Deque;
import java.util.LinkedList;

public class Leedcode662二叉树最大宽度 {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = new TreeNode(2);
        node.right = new TreeNode(3);
        node.left.left = new TreeNode(4);
        System.out.println(widthOfBinaryTree(node));
    }

    public static int widthOfBinaryTree(TreeNode root) {
        //如果根节点为空，返回0
        if (root == null){
            return 0;
        }
        //走到这里说明至少存在一个节点，计算他的左右子节点的index，
        Deque<TreeNode> queue = new LinkedList();
        Deque queue1 = new LinkedList<>();
        queue.offer(root);
        queue1.offer(1);
        int width = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            int temWidth = 0,left = 0,right = 0;
            boolean flag =false;
            while (size-- > 0){
                TreeNode node =  queue.pollFirst();
                int pos = (int) queue1.pollFirst();
                if (!flag){
                    flag = true;
                    left = pos;
                }
                right = pos;
                temWidth = Math.max(temWidth,(right - left) + 1);
                if (node.left != null){
                    queue.offerLast(node.left);
                    queue1.offerLast(2*pos);
                }
                if (node.right != null){
                    queue.offerLast(node.right);
                    queue1.offerLast(2*pos+1);
                }
            }
            width = Math.max(width,temWidth);
        }
        return width;
    }
}
